
public class node {
	private int t;							//the t element of the tree
	private int size;						//number of elements in the node
	private boolean isLeaf;					//Is this node a leaf
	private int[] data;						//Array of the data
	private node[] sons;					//Array of pointers to the next levels
	private node previous;					//Link to the previous node (if this node is a leaf)
	private node next;						//Link to the next node (if this node is a leaf)
	private int min_gap = 0;
	
	public node(int t, boolean isLeaf){
		this.t 			= t;
		this.size 		= 0;
		this.isLeaf 	= isLeaf;
		this.data 		= new int[t];
		this.sons 		= new node[t + 1];
		this.previous	= null;
		this.next		= null;
		
	}
	// returns where or not there is free space in the node.
	public boolean isFull(){
		return this.t - 1 == size;
	}
	
	
	
	/**
	 * @param t
	 * @param size
	 * @param isLeaf
	 * @param data
	 * @param sons
	 * @param previous
	 * @param next
	 * @param min_gap
	 */
	public node(node n) {
		this.t = n.t;
		this.size = n.size;
		this.isLeaf = n.isLeaf;
		this.data = n.data;
		this.sons = n.sons;
		this.previous = n.previous;
		this.next = n.next;
		this.min_gap = n.min_gap;
	}
	
	public int getSize() {
		return size;
	}
	
	public void incSize() {
		this.size++;
	}

	public boolean isLeaf() {
		return isLeaf;
	}
	
	public int[] getData() {
		return data;
	}
	
	public int getDataOfIndex(int i) {
		return this.data[i];
	}
	
	public node getSonInIndex(int i) {
		return sons[i];
	}
	
	public void setData(int index, int data) {
		this.data[index] = data;
	}
	
	public void setSon(int index, node son) {
		this.sons[index] = son;
	}
	
	
	//setter for next node.
	public void setNext (node next){
		this.next = next;
	}
	
	//setter for previous node.
	public void setPrevious (node previous){
			this.previous = previous;
	}
	
	//getter for next node.
	public node getNext (){
		return this.next;
	}
	
	//getter for previous node.
	
	public node getPrevious (){
		return this.previous;
	}
	
	public int insertValueFixSons ( NodeNValue nodeAndValue ){
		int minGapHelper = -1;
		int minGapLeft = -1;
		int minGapRight = -1;
		NodeNValue temp = new NodeNValue();
		NodeNValue valueToMoveForward = new NodeNValue(nodeAndValue) ;
		boolean enteredLoop = false;
		//boolean movedForward = false;
		
		if ( this.size != 0 ){
			for (int i = 0 ; i < this.size; i++){
				
				if ( valueToMoveForward.value < this.data[i] ){
					enteredLoop = true;
					temp.value 	= this.data[i];
					temp.n 		= this.sons[i + 1];
					this.data[i] 		= valueToMoveForward.value;
					this.sons[i + 1] 	= valueToMoveForward.n;
					if (i == 0 && this.previous != null){
						minGapLeft = Math.abs((this.previous.data[this.previous.size - 1] ) - this.data[i]);
						
					}else if (i > 0){
						minGapLeft = Math.abs(this.data[i] - this.data[i - 1]);
					}
					minGapRight = Math.abs(temp.value - this.data[i]);
					
					if (minGapRight != -1 && minGapLeft != -1){
						minGapHelper = Math.min(minGapRight, minGapLeft);
					}
					valueToMoveForward 	= new NodeNValue(temp);
					//movedForward = true;
				}
			}
			
			//if ( false == movedForward ){
			this.data[this.size] = valueToMoveForward.value;
			this.sons[this.size + 1] = valueToMoveForward.n;
			if (this.sons[this.size + 1] != null){
				this.sons[this.size + 1].previous = this.sons[this.size];
			}
			
			
			 
			if ((!enteredLoop)	&&
				(this.size > 0)){
				minGapHelper =Math.abs(this.data[this.size] - this.data[this.size - 1]);  
			}
			
			if (enteredLoop){
				
			}
			//}
			
		}else{
			this.data[0] = nodeAndValue.value;
			this.sons[0] = nodeAndValue.n;
		}
	
		this.size++;
		return minGapHelper;
	}
	
	public NodeNValue split( int insertValue, node newSon, boolean isRemoveMiddle ){
		int minGapHelper = -1;
		NodeNValue rightHalfAndMiddleValue = new NodeNValue();
		
		rightHalfAndMiddleValue.n 		= new node(t, this.isLeaf);
		rightHalfAndMiddleValue.n.next 	= this.next;
		this.next = rightHalfAndMiddleValue.n;
		rightHalfAndMiddleValue.n.previous 	= this;
		NodeNValue insertNodeNValue 		= new NodeNValue();
		
		insertNodeNValue.n 		= newSon;
		insertNodeNValue.value 	= insertValue;
		
		minGapHelper = insertValueFixSons(insertNodeNValue);
		rightHalfAndMiddleValue.minGap = minGapHelper;
		int indexOfHalfTRoundedUp = (t/2) + (t%2) - 1;
		rightHalfAndMiddleValue.value = this.data[indexOfHalfTRoundedUp];
		
		if ( isRemoveMiddle ){

			int i;
			for ( i = indexOfHalfTRoundedUp + 1 ; i < t ; i++){
				rightHalfAndMiddleValue.n.data[i - (indexOfHalfTRoundedUp + 1)] = this.data[i];
				rightHalfAndMiddleValue.n.sons[i - (indexOfHalfTRoundedUp + 1)] = this.sons[i];
				this.sons[i] = null;
			}
			rightHalfAndMiddleValue.n.sons[i - (indexOfHalfTRoundedUp + 1)] = this.sons[i];
			
			this.size = indexOfHalfTRoundedUp;
			
			
		}else{
			for (int i = indexOfHalfTRoundedUp + 1 ; i < t ; i++){
				rightHalfAndMiddleValue.n.data[i - (indexOfHalfTRoundedUp + 1 )] = this.data[i];
			}
			this.size = indexOfHalfTRoundedUp + 1;
		}
		
		rightHalfAndMiddleValue.n.size = t/2;
		return rightHalfAndMiddleValue;
	}
	
	
}
